#include <stdio.h>
#include <algorithm>
#include <queue>
#include <functional>

#define INFINITY  0x00FFFFFFFFFFFFFFLL
#define MAX_NODES 1000
#define MAX_EDGES 20000

typedef unsigned short vid_t;
typedef unsigned short eid_t;

/* We use a compact format to store the graph. */
struct node 
{
    eid_t first_edge;
    vid_t num_edges;
    int weight;
};
static node nodes[MAX_NODES+1];
static int num_nodes;

/* An edge is stored as (u, v) => weight. */
struct edge_t : public std::pair<std::pair<vid_t,vid_t>, int>
{
    typedef std::pair<std::pair<vid_t,vid_t>, int> base;
    edge_t() { }
    edge_t(vid_t v1, vid_t v2, int weight) 
        : base(std::make_pair(std::make_pair(v1, v2), weight)) { }
    vid_t v1() const { return base::first.first; }
    vid_t v2() const { return base::first.second; }
    int weight() const { return base::second; }
};
static edge_t edges[MAX_EDGES*2+1];
static int num_edges;

static bool read_graph()
{
    if (!(scanf("%d %d", &num_nodes, &num_edges) == 2 && num_nodes > 0))
        return false;

    /* Read node weights. */
    for (int i = 1; i <= num_nodes; i++)
        scanf("%d", &nodes[i].weight);

    /* Read edge and edge weights. */
    for (int j = 1; j <= num_edges; j++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        edges[j] = edge_t((vid_t)u, (vid_t)v, w);
        edges[num_edges+j] = edge_t((vid_t)v, (vid_t)u, w);
    }

    /* Create adjacency list. */
    std::sort(edges+1, edges+2*num_edges+1);
    eid_t j = 1;
    for (vid_t i = 1; i <= num_nodes; i++)
    {
        nodes[i].first_edge = j;
        nodes[i].num_edges = 0;
        for (; edges[j].v1() == i; j++)
            ++nodes[i].num_edges;
    }
    return true;
}

#define MAX_QUERIES 20000
static std::pair<vid_t,vid_t> queries[MAX_QUERIES];
static long long answers[MAX_QUERIES];
static int num_queries;

static void read_queries()
{
    scanf("%d", &num_queries);
    for (int i = 0; i < num_queries; i++)
    {
        int start, end;
        scanf("%d %d", &start, &end);
        queries[i].first = (vid_t)start;
        queries[i].second = (vid_t)end;
        answers[i] = INFINITY;
    }
}

/* In each pass, we start from a given node u and finds the shortest distance
 * from u to every other node v, such that we never pass any node with a 
 * weight higher than u. After that, we update the optimal cost for all the
 * queries.
 */
static long long distance[MAX_NODES+1]; /* d[v] = shortest path from u to v */

static void dijkstra(vid_t start, long long d[MAX_NODES+1])
{
    /* Creates a priority queue of nodes. */
    typedef std::pair<long long, vid_t> dijkstra_node; /* weight => v */
    std::priority_queue<dijkstra_node,
                        std::vector<dijkstra_node>,
                        std::greater<dijkstra_node> > q;

    /* Mark all nodes as unvisited and initialize all d[v] to +inf. */
    bool visited[MAX_NODES+1] = { false };
    for (int i = 1; i <= num_nodes; i++)
        d[i] = INFINITY;

    /* Push the start node into the priority queue. */
    q.push(dijkstra_node(0, start));
    d[start] = 0;

    /* Extract nodes until all nodes are visited. */
    while (!q.empty())
    {
        vid_t u = q.top().second;
        q.pop();
        if (visited[u])
            continue;
        visited[u] = true;

        for (int i = 0; i < nodes[u].num_edges; i++)
        {
            const edge_t &e = edges[nodes[u].first_edge + i];
            vid_t v = e.v2();

            /* Skip this node if it's already visited. */
            if (visited[v])
                continue;

            /* Skip this node if it has a higher weight than 'start'. */
            if (nodes[v].weight > nodes[start].weight)
                continue;

            /* Compute the distance from start to v via u. */
            int w = e.weight();
            if (d[u] + w >= d[v])
                continue;

            /* Update the minimum distance from start to v. */
            d[v] = d[u] + w;
            q.push(dijkstra_node(d[v], v));
        }
    }
}

/* Try improve the answers to the queries by assuming u as the node with
 * the highest weight along the shortest path.
 */
static void improve_answers(vid_t high)
{
    for (int i = 0; i < num_queries; i++)
    {
        vid_t u = queries[i].first, v = queries[i].second;
        long long d = distance[u] + distance[v] + nodes[high].weight;
        if (d < answers[i])
        {
#if 0
            printf("Improve d(%d, %d) via %d to %lld\n", u, v, high, d);
#endif
            answers[i] = d;
        }
    }
}

int main()
{
#if 0
    freopen("input/4046_ext.txt", "r", stdin);
#endif
    while (read_graph())
    {
        read_queries();

        /* Compute the shortest path assuming each node as the highest-weight
         * node. Improve the answers iteratively.
         */
        for (vid_t u = 1; u <= num_nodes; u++)
        {
            dijkstra(u, distance);
            improve_answers(u);
        }

        /* Print answers. */
        for (int i = 0; i < num_queries; i++)
        {
            printf("%lld\n", (answers[i] >= INFINITY)? -1 : answers[i]);
        }
        printf("\n");
    }
    return 0;
}